package com.example.algorithm.tree.binaryTree;

import com.example.algorithm.linear.queue.Queue;
import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.concurrent.locks.ReentrantReadWriteLock;

@Slf4j
public class BinaryTree<Key extends Comparable<Key>, Value> {
    //记录根节点
    private Node root;
    //记录树种元素的个数
    private int N;

    private ReentrantReadWriteLock rw = new ReentrantReadWriteLock();

    private ReentrantReadWriteLock.ReadLock readLock = rw.readLock();

    private ReentrantReadWriteLock.WriteLock writeLock = rw.writeLock();


    @Data
    private class Node {
        //存储键
        public Key key;

        //存储值
        public Value value;

        //左子结点
        public Node left;

        //右子节点
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    //获取树中元素的个数
    public int size() {
        readLock.lock();
        try {
            return N;
        } finally {
            readLock.unlock();
        }
    }

    //向树中添加元素key-value
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    //向树中添加元素key-value
    public Node put(Node x, Key key, Value value) {

        writeLock.lock();

        try {

            if (x == null) {
                N++;
                return new Node(key, value, null, null);
            }
            //如果子树不为空
            //比较x结点的键Key的大小
            int cmp = key.compareTo(x.key);
            if (cmp > 0) {
                //key > x结点的键，继续找x结点的右子树
                x.right = put(x.right, key, value);
            } else if (cmp < 0) {
                //key < x结点的键,继续x结点的左子树
                x.left = put(x.left, key, value);
            } else {
                //如果key = x结点的值，替换x结点的值
                x.value = value;
            }

            return x;
        } finally {
            writeLock.unlock();
        }

    }

    //查询树中指定key对应的value
    public Value get(Key key) {
        return get(root, key);
    }

    //从指定的x中，查找key对应的值
    public Value get(Node x, Key key) {

        readLock.lock();

        try {
            //如果x为空
            if (x == null) {
                return null;
            }
            //如果子树不为空
            //比较x结点的键Key的大小
            int cmp = key.compareTo(x.key);
            if (cmp > 0) {
                //key > x结点的键，继续找x结点的右子树
                return get(x.right, key);
            } else if (cmp < 0) {
                //key < x结点的键,继续x结点的左子树
                return get(x.left, key);
            } else {
                //如果key = x结点的值，替换x结点的值
                return x.value;
            }
        } finally {
            readLock.unlock();
        }

    }

    //删除树中key对应的value
    public void delete(Key key) {
        delete(root, key);
    }

    //删除指定结点中，key对应的value
    public Node delete(Node x, Key key) {

        writeLock.lock();

        try {
            //x树为null
            if (x == null) {
                return null;
            }
            //x树不为null
            //如果子树不为空
            //比较x结点的键Key的大小
            int cmp = key.compareTo(x.key);
            if (cmp > 0) {
                //key > x结点的键，继续找x结点的右子树
                x.right = delete(x.right, key);
            } else if (cmp < 0) {
                //key < x结点的键,继续x结点的左子树
                x.left = delete(x.left, key);
            } else {
                //元素个数-1
                N--;
                //如果key = x结点的值，完成真正的删除

                //找到右子树中最小的结点
                if (x.right == null) {
                    return x.left;
                }

                if (x.left == null) {
                    return x.right;
                }

                Node minNode = x.right;
                while (minNode.left != null) {
                    minNode = minNode.left;
                }

                //删除右子树最小的结点
                Node n = x.right;
                while (n.left != null) {
                    if (n.left.left == null) {
                        n.left = null;
                    } else {
                        n = n.left;
                    }
                }

                //让x结点的左子树成为mineNode的左子树
                minNode.left = x.left;
                //让x结点的右子树成为mineNode的右子树
                minNode.right = x.right;
                //让x父结点指向mineNode
                x = minNode;

            }

            return x;

        } finally {
            writeLock.unlock();
        }
    }

    //查找整个树中最小的键
    public Key min() {
        return min(root).key;
    }

    //在指定树x中找出最小键所在的结点
    private Node min(Node x) {

        //判断x有没有左子节点，如果有，继续向左找，如果没有，x就是最小
        if (x.left != null) {
            return min(x.left);
        } else {
            return x;
        }
    }

    //查找整个树中最大的键
    public Key max() {
        return max(root).key;
    }

    //在指定树x中找出最小键所在的结点
    private Node max(Node x) {

        //判断x有没有左子节点，如果有，继续向左找，如果没有，x就是最小
        if (x.right != null) {
            return max(x.left);
        } else {
            return x;
        }
    }

    //前序遍历：获取整个树中所有的键
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        preErgodic(root,keys);
        return keys;
    }

    //前序遍历：获取指定树x所有的键，放在keys队列中
    public void preErgodic(Node x, Queue<Key> keys){
        if (x == null) {
            return;
        }
        //把x结点的key放入keys中
        keys.enqueue(x.key);
        //递归遍历左子树
        if (x.left != null){
            preErgodic(x.left,keys);
        }

        //递归遍历右子树
        if (x.right != null){
            preErgodic(x.right,keys);
        }
    }

    //中序遍历
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(root,keys);
        return keys;
    }

    //中序遍历
    public void midErgodic(Node x,Queue<Key> keys){
        if (x == null){
            return;
        }

        //递归遍历左子树
        if (x.left != null){
            midErgodic(x.left,keys);
        }

        //把x结点的key放入keys中
        keys.enqueue(x.key);

        //递归遍历右子树
        if (x.right != null){
            midErgodic(x.right,keys);
        }

    }

    //后序遍历
    public Queue<Key> afterErgodic(){
        Queue<Key> keys = new Queue<>();
        afterErgodic(root,keys);
        return keys;
    }

    //后序遍历
    public void afterErgodic(Node x,Queue<Key> keys){
        if (x == null){
            return;
        }

        //递归遍历左子树
        if (x.left != null){
            afterErgodic(x.left,keys);
        }



        //递归遍历右子树
        if (x.right != null){
            afterErgodic(x.right,keys);
        }

        //把x结点的key放入keys中
        keys.enqueue(x.key);

    }

    //层序遍历
    public Queue<Key> layerErgodic(){
        //定义两个队列,树中的键和树中的结点
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();

        //放入根节点
        nodes.enqueue(root);

        while (!nodes.isEmpty()){
            //从队列中弹出结点，把key放入keys中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //判断当前结点有没有左子节点
            if (n.left != null){
                nodes.enqueue(n.left);
            }
            //判断当前结点有没有右子节点
            if (n.right != null){
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }

    //获取整个树最大深度
    public int maxDepth(){
        return maxDepth(root);
    }

    //获取指定树最大深度
    public int maxDepth(Node x){

        if (x == null) {
            return 0;
        }

        int maxL = 0;//左
        int maxR = 0;//右

        //计算左子树最大深度
        if (x.left != null){
            maxL = maxDepth(x.left);
        }
        //计算右子树最大深度
        if (x.right != null){
            maxR = maxDepth(x.right);
        }
        //比较，取较大值
        if (maxR >= maxL){
            return maxR + 1;
        }else {
            return maxL + 1;
        }

    }

}
